public class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return 0;
        }

        int end = 0;
        int maxEnd = nums[0];
        int count = 0;
        while (end < len) {
            count++;
            int num = 0;
            while (end < len && end <= maxEnd) {
                num = Math.max(num, end + nums[end]);
                end++;
            }
            maxEnd = num;
        }

        return count;
    }

    public int jump2(int[] nums) {
        int len = nums.length;

        //以i位置为结尾的最少次数
        int[] dp = new int[len];

        for (int i = 1; i < len; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] + j >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[len - 1];
    }
}
